package leetcode.code1339;

import leetcode.helper.tree.TreeNode;

public class Solution {
	long sum;
	long ans;
	int mod = (int) 1e9 + 7;

	public int maxProduct(TreeNode root) {
		sum = 0;
		this.sum(root);
		this.f(root);
		return (int) (ans % mod);
	}

	private long f(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int val = root.val;
		long left = this.f(root.left);
		long right = this.f(root.right);
		if (left != 0) {
			long ans1 = 1l * (this.sum - left) * left;
			ans = Math.max(ans, ans1);
		}
		if (right != 0) {
			long ans2 = 1l * (this.sum - right) * right;
			ans = Math.max(ans, ans2);
		}
		return left + right + val;
	}

	private void sum(TreeNode root) {
		if (root == null) {
			return;
		}
		sum += 1l * root.val;
		this.sum(root.left);
		this.sum(root.right);
	}
}
